#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/**
 * Definition for singly-linked list.
 */
struct ListNode {
	int val;
	struct ListNode* next;
};
typedef struct ListNode list_node, *list_node_p;

struct ListNode* reverseKGroup(struct ListNode* head, int k);
void reverse(list_node_p head, int k);

int main()
{
	return 0;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k)
{
	if (k == 1)
		return head;

	list_node hair = { 0, head };
	reverse(&hair, k);

	return hair.next;
}

void reverse(list_node_p head, int k)
{
	list_node_p aux = head;
	int times = k;
	while (times--)
		if (!aux)
			return;
		else
			aux = aux->next;
	if (!aux)
		return;

	list_node_p p1 = head->next, p2 = p1->next, p3 = p2->next;
	for (; p1 != aux; p1 = p2, p2 = p3, p3 = p3 ? p3->next : NULL)
		p2->next = p1;

	list_node_p tail_new = head->next;
	tail_new->next = p2;
	head->next = p1;

	reverse(tail_new, k);
}

struct ListNode* yuki(struct ListNode* head, int k)
{
	struct ListNode* slow = head;
	while (true) {
		struct ListNode* fast = slow;
		int cnt = k;
		while (cnt-- && fast) fast = fast->next;
		if (cnt != -1) return head;
		struct ListNode* dummy = slow;
		slow = dummy->next;
		for (int i = 0; i != k; i++) {
			struct ListNode* temp = dummy->next;
			dummy->next = fast;
			fast = dummy;
			if (i != k- 1) dummy = temp;
		}
	}
}
